package cn.algorithm;


import cn.controller.GameAction;
import cn.controller.PlayerObject;
import cn.controller.PlayingEntity;
import cn.view.Main;

import java.awt.*;
import java.math.BigInteger;
import java.text.SimpleDateFormat;
import java.util.*;


public class AlphaBetaAI implements PlayingEntity {
    private final int RED = 1, BLUE = 2, EMPTY = 0;
    private int MAX_DEPTH = 3, BEAM_SIZE = 6;
    private int[][] pieces;
    private HashMap lookUpTable;
    private int team;
    private LinkedList<AIHistoryObject> history = new LinkedList<>();
    private final int gridSize;
    private String name;
    private Color color;
    private long timeLeft;
    private final Main game;
    private boolean skipMove = false;
    private EvaluationNode[][] nodesArray;
    public Record record = new Record();


    public AlphaBetaAI(int team, Main game) {
        this.team = team;
        this.game = game;
        if (team == 1) {
            color = Color.RED;
        } else {
            color = Color.blue;
        }
        name = "AI";
        gridSize = game.gridSize;
        pieces = new int[gridSize + 2][gridSize + 2];
        for (int i = 1; i < pieces.length - 1; i++) {
            pieces[i][0] = RED;
            pieces[0][i] = BLUE;
            pieces[i][pieces.length - 1] = RED;
            pieces[pieces.length - 1][i] = BLUE;
        }
        lookUpTable = new HashMap();
    }

    @Override
    public void getPlayerTurn() {
        skipMove = false;
        AIHistoryObject state = new AIHistoryObject(pieces, lookUpTable);
        history.add(state);
        int moveNumber = game.moveNumber;

        Point lastMove;
        try {
            if (moveNumber > 1)
                lastMove = new Point(gridSize - 1 - game.moveList.getMove().getY(), game.moveList.getMove().getX());
            else lastMove = null;
        } catch (Exception e) {
            lastMove = null;
        }
        // System.out.println("Last move: " + lastMove);
        if (lastMove == null) {
            pieces[pieces.length / 2][pieces.length / 2] = team;
            if (!skipMove) {
                GameAction.makeMove(this, (byte) team, new Point(pieces.length / 2 - 1, pieces.length / 2 - 1), game);
                record.records.add(new Point(pieces.length / 2 - 1, pieces.length / 2 - 1));
            }

        } else {
            // System.out.println("1(" + lastMove);
            record.records.add(lastMove);
            pieces[lastMove.x + 1][lastMove.y + 1] = team == 1 ? 2 : 1;
            Point bestMove = getBestMove();

            pieces[bestMove.x][bestMove.y] = team;
            int x = bestMove.x - 1;
            int y = bestMove.y - 1;
            record.records.add(new Point(x, y));
            // System.out.println("2(" + bestMove);

            if (!skipMove) GameAction.makeMove(this, (byte) team, new Point(y, gridSize - 1 - x), game);
        }
    }

    @Override
    public void undoCalled() {
        if (history.size() > 0) {
            AIHistoryObject previousState = history.get(history.size() - 1);
            pieces = previousState.pieces;
            lookUpTable = previousState.lookUpTable;
            history.remove(history.size() - 1);
        }
        skipMove = true;
    }

    @Override
    public void newgameCalled() {
        skipMove = true;
    }

    @Override
    public boolean supportsUndo() {
        if (team == 1) {
            return game.player2 instanceof PlayerObject;
        } else {
            return game.player1 instanceof PlayerObject;
        }
    }

    @Override
    public boolean supportsNewgame() {
        return true;
    }

    private Point getBestMove() {
        int bestValue = team == RED ? Integer.MIN_VALUE :
                Integer.MAX_VALUE;
        int bestRow = -1;
        int bestColumn = -1;

        for (int i = 1; i < pieces.length - 1; i++) {
            for (int j = 1; j < pieces.length - 1; j++) {
                if (pieces[i][j] != 0)
                    continue;
                pieces[i][j] = team;
                int value = expand(1, bestValue, team == RED ? BLUE :
                        RED, nodesArray);
                pieces[i][j] = 0;
                if (team == RED && value > bestValue) {
                    bestValue = value;
                    bestRow = i;
                    bestColumn = j;
                } else if (team == BLUE && value < bestValue) {
                    bestValue = value;
                    bestRow = i;
                    bestColumn = j;
                }
            }
        }
        return new Point(bestRow, bestColumn);
    }

    private int expand(int depth, int previousBest, int currentColour, EvaluationNode[][] nodesArray) {
        if (depth == MAX_DEPTH)
            return evaluate();
        int bestValue = currentColour == RED ? Integer.MIN_VALUE :
                Integer.MAX_VALUE;

        Iterator iter = getMoves().iterator();

        for (int i = 0; i < BEAM_SIZE && iter.hasNext(); i++) {
            // Gets the move value of the next move.
            Move nextMove = (Move) iter.next();
            pieces[nextMove.row][nextMove.column] = currentColour;
            int value = expand(depth + 1, bestValue,
                    currentColour == RED ? BLUE :
                            RED, nodesArray);
            pieces[nextMove.row][nextMove.column] = 0;

            if (currentColour == RED && value > bestValue)
                bestValue = value;
            else if (currentColour == BLUE && value < bestValue)
                bestValue = value;

            if (currentColour == RED && bestValue > previousBest ||
                    currentColour == BLUE && bestValue < previousBest)
                return bestValue;
        }

        if (bestValue == Integer.MAX_VALUE || bestValue == Integer.MIN_VALUE)
            bestValue = evaluate();
        return bestValue;
    }

    private ArrayList getMoves() {
        nodesArray = new EvaluationNode[pieces.length][pieces.length];
        EvaluationNode.buildEvaluationBoard(pieces, nodesArray);

        int[][] redA = new int[pieces.length][pieces.length];
        int[][] redB = new int[pieces.length][pieces.length];
        int[][] blueA = new int[pieces.length][pieces.length];
        int[][] blueB = new int[pieces.length][pieces.length];
        for (int i = 0; i < pieces.length; i++) {
            for (int j = 0; j < pieces.length; j++) {
                redA[i][j] = 100000;
                redB[i][j] = 100000;
                blueA[i][j] = 100000;
                blueB[i][j] = 100000;
            }
        }

        redA[0][0] = 0;
        redA[redA.length - 1][0] = 0;
        redB[0][redB.length - 1] = 0;
        redB[redB.length - 1][redB.length - 1] = 0;
        blueA[0][0] = 0;
        blueA[0][blueA.length - 1] = 0;
        blueB[blueB.length - 1][0] = 0;
        blueB[blueB.length - 1][blueB.length - 1] = 0;

        boolean found = true;
        while (found) {
            found = false;
            for (int j = 1; j < redA.length - 1; j++) {
                for (int i = 1; i < redA.length - 1; i++) {
                    if (redA[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;
                    Iterator iter = nodesArray[i][j].redNeighbours.iterator();
                    while (iter.hasNext()) {

                        EvaluationNode next = (EvaluationNode) iter.next();
                        int number = redA[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (redA[i][j] != secondMin + 1) {
                            found = true;
                            redA[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }

        found = true;
        while (found) {
            found = false;
            for (int j = redB.length - 2; j > 0; j--) {
                for (int i = 1; i < redB.length - 1; i++) {
                    if (redB[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;
                    Iterator iter = nodesArray[i][j].redNeighbours.iterator();

                    while (iter.hasNext()) {
                        EvaluationNode next = (EvaluationNode) iter.next();
                        int number = redB[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (redB[i][j] != secondMin + 1) {
                            found = true;
                            redB[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }

        found = true;
        while (found) {
            found = false;
            for (int i = 1; i < blueA.length - 1; i++) {
                for (int j = 1; j < blueA.length - 1; j++) {
                    if (blueA[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;
                    Iterator iter = nodesArray[i][j].blueNeighbours.iterator();

                    while (iter.hasNext()) {
                        EvaluationNode next = (EvaluationNode) iter.next();
                        int number = blueA[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (blueA[i][j] != secondMin + 1) {
                            found = true;
                            blueA[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }
        found = true;
        while (found) {
            found = false;
            for (int i = 1; i < blueB.length - 1; i++) {
                for (int j = blueB.length - 2; j > 0; j--) {
                    if (blueB[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;
                    Iterator iter = nodesArray[i][j].blueNeighbours.iterator();

                    while (iter.hasNext()) {
                        EvaluationNode next = (EvaluationNode) iter.next();
                        int number = blueB[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (blueB[i][j] != secondMin + 1) {
                            found = true;
                            blueB[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }
        ArrayList moves = new ArrayList();

        for (int i = 1; i < pieces.length - 1; i++) {
            for (int j = 1; j < pieces.length - 1; j++) {
                if (pieces[i][j] != 0)
                    continue;
                moves.add(new Move(i, j, redA[i][j]
                        + redB[i][j]
                        + blueA[i][j]
                        + blueB[i][j]));
            }
        }

        Collections.sort(moves);
        return moves;
    }

    /**
     * Evaluates the current board.
     *
     * @return the board value
     */
    private int evaluate() {

        BigInteger piecesString = piecesString();
        Integer piecesValue = (Integer) lookUpTable.get(piecesString);
        if (piecesValue != null)
            return piecesValue.intValue();
        nodesArray = new EvaluationNode[pieces.length][pieces.length];
        EvaluationNode.buildEvaluationBoard(pieces, nodesArray);

        int[][] redA = new int[pieces.length][pieces.length];
        int[][] redB = new int[pieces.length][pieces.length];
        int[][] blueA = new int[pieces.length][pieces.length];
        int[][] blueB = new int[pieces.length][pieces.length];
        for (int i = 0; i < pieces.length; i++) {
            for (int j = 0; j < pieces.length; j++) {
                redA[i][j] = 100000;
                redB[i][j] = 100000;
                blueA[i][j] = 100000;
                blueB[i][j] = 100000;
            }
        }

        redA[0][0] = 0;
        redA[redA.length - 1][0] = 0;
        redB[0][redB.length - 1] = 0;
        redB[redB.length - 1][redB.length - 1] = 0;
        blueA[0][0] = 0;
        blueA[0][blueA.length - 1] = 0;
        blueB[blueB.length - 1][0] = 0;
        blueB[blueB.length - 1][blueB.length - 1] = 0;

        boolean found = true;
        while (found) {
            found = false;

            for (int j = 1; j < redA.length - 1; j++) {
                for (int i = 1; i < redA.length - 1; i++) {
                    if (redA[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;

                    int min = 100000;
                    int secondMin = 100000;

                    for (Object o : nodesArray[i][j].redNeighbours) {

                        EvaluationNode next = (EvaluationNode) o;
                        int number = redA[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (redA[i][j] != secondMin + 1) {
                            found = true;
                            redA[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }

        found = true;
        while (found) {
            found = false;
            for (int j = redB.length - 2; j > 0; j--) {
                for (int i = 1; i < redB.length - 1; i++) {
                    if (redB[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;

                    for (Object o : nodesArray[i][j].redNeighbours) {
                        EvaluationNode next = (EvaluationNode) o;
                        int number = redB[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (redB[i][j] != secondMin + 1) {
                            found = true;
                            redB[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }

        found = true;
        while (found) {
            found = false;
            for (int i = 1; i < blueA.length - 1; i++) {
                for (int j = 1; j < blueA.length - 1; j++) {
                    if (blueA[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;

                    for (Object o : nodesArray[i][j].blueNeighbours) {
                        EvaluationNode next = (EvaluationNode) o;
                        int number = blueA[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (blueA[i][j] != secondMin + 1) {
                            found = true;
                            blueA[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }

        found = true;
        while (found) {
            found = false;
            for (int i = 1; i < blueB.length - 1; i++) {
                for (int j = blueB.length - 2; j > 0; j--) {
                    if (blueB[i][j] != 100000)
                        continue;
                    if (pieces[i][j] != 0)
                        continue;
                    int min = 100000;
                    int secondMin = 100000;

                    for (Object o : nodesArray[i][j].blueNeighbours) {
                        EvaluationNode next = (EvaluationNode) o;
                        int number = blueB[next.row][next.column];
                        if (number < secondMin) {
                            secondMin = number;
                            if (number < min) {
                                secondMin = min;
                                min = number;
                            }
                        }
                    }
                    if (secondMin < 100) {
                        if (blueB[i][j] != secondMin + 1) {
                            found = true;
                            blueB[i][j] = secondMin + 1;
                        }
                    }
                }
            }
        }

        int redPotential = 100000;
        int bluePotential = 100000;
        int redMobility = 0;
        int blueMobility = 0;
        for (int i = 1; i < redA.length - 1; i++) {
            for (int j = 1; j < redA.length - 1; j++) {
                if (pieces[i][j] == 0) {
                    if (redA[i][j] + redB[i][j] < redPotential) {
                        redPotential = redA[i][j] + redB[i][j];
                        redMobility = 1;
                    } else if (redA[i][j] + redB[i][j] == redPotential)
                        redMobility++;
                    if (blueA[i][j] + blueB[i][j] < bluePotential) {
                        bluePotential = blueA[i][j] + blueB[i][j];
                        blueMobility = 1;
                    } else if (blueA[i][j] + blueB[i][j] == bluePotential)
                        blueMobility++;
                }
            }
        }

        int i = 100 * (bluePotential - redPotential) - (blueMobility - redMobility);
        lookUpTable.put(piecesString, i);

        return i;
    }

    private BigInteger piecesString() {
        BigInteger value =
                new BigInteger(Integer.toString((pieces.length - 2)));
        for (int i = 1; i < pieces.length - 1; i++) {
            for (int j = 1; j < pieces.length - 1; j++) {
                value = value.multiply(new BigInteger("3"));
                value = value.add(
                        new BigInteger(Integer.toString(pieces[i][j])));
            }
        }
        return value;
    }

    @Override
    public void quit() {
        skipMove = true;
    }

    @Override
    public void win() {
        System.out.println("对局结束");
    }

    @Override
    public void lose() {

        Date day = new Date();
        SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH-mm");
        String gameTime = df.format(day);
        System.out.println(gameTime);
    }

    @Override
    public boolean supportsSave() {
        return false;
    }

    @Override
    public void endMove() {
        skipMove = true;
    }

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public Color getColor() {
        return color;
    }

    @Override
    public void setColor(Color color) {
        this.color = color;
    }

    @Override
    public void setMove(Object o, Point hex) {
    }

    public class AIHistoryObject {
        int[][] pieces;
        HashMap lookUpTable;

        public AIHistoryObject(int[][] pieces, HashMap lookUpTable) {
            this.pieces = new int[pieces.length][pieces.length];
            for (int i = 0; i < pieces.length; i++) {
                for (int j = 0; j < pieces.length; j++) {
                    this.pieces[i][j] = pieces[i][j];
                }
            }
            this.lookUpTable = lookUpTable;
        }
    }

}

class Move implements Comparable {
    public int row;
    public int column;
    private final int value;

    public Move(int row, int column, int value) {
        this.row = row;
        this.column = column;
        this.value = value;
    }

    public int compareTo(Object other) {
        return this.value - ((Move) other).value;
    }
}

class EvaluationNode {
    public HashSet redNeighbours;
    public HashSet blueNeighbours;
    public int row;
    public int column;

    public EvaluationNode(int row, int column) {
        this.row = row;
        this.column = column;
        redNeighbours = new HashSet();
        blueNeighbours = new HashSet();
    }

    public static void buildEvaluationBoard(int[][] pieces, EvaluationNode[][] nodesArray) {
        for (int i = 0; i < nodesArray.length; i++)
            for (int j = 0; j < nodesArray.length; j++)
                nodesArray[i][j] = new EvaluationNode(i, j);

        for (int i = 0; i < nodesArray.length; i++)
            for (int j = 0; j < nodesArray.length; j++) {
                if (pieces[i][j] != 0)
                    continue;
                nodesArray[i][j].redNeighbours = nodesArray[i][j].getNeighbours(1, new HashSet(), nodesArray, pieces);
                nodesArray[i][j].redNeighbours.remove(nodesArray[i][j]);
                nodesArray[i][j].blueNeighbours = nodesArray[i][j].getNeighbours(2, new HashSet(), nodesArray, pieces);
                nodesArray[i][j].blueNeighbours.remove(nodesArray[i][j]);
            }
    }

    private HashSet getNeighbours(int colour, HashSet piecesVisited, EvaluationNode[][] nodesArray, int[][] pieces) {

        if (piecesVisited.contains(this))
            return new HashSet();
        HashSet returnValue = new HashSet();
        if (pieces[row][column] == colour)
            piecesVisited.add(this);

        for (int a = -1; a <= 1; a++) {
            for (int b = -1; b <= 1; b++) {
                if (a + b == 0)
                    continue;
                if (row + a < 0 || row + a == nodesArray.length ||
                        column + b < 0 || column + b == nodesArray.length)
                    continue;

                if (pieces[row + a][column + b] == 0)
                    returnValue.add(nodesArray[row + a][column + b]);

                else if (pieces[row + a][column + b] != colour)
                    continue;
                else
                    returnValue.addAll(nodesArray[row + a][column + b].getNeighbours(colour, piecesVisited, nodesArray, pieces));
            }
        }
        return returnValue;
    }

    public int hashCode() {
        return row * 100 + column;
    }

    public boolean equals(Object other) {
        EvaluationNode otherNode = (EvaluationNode) other;
        return row == otherNode.row && column == otherNode.column;
    }
}